package inabit.compiler.parser.table;

import inabit.compiler.parser.SemanticAction;
import inabit.compiler.parser.grammar.Grammar;
import inabit.compiler.parser.grammar.NonTerminal;
import inabit.compiler.parser.grammar.Production;
import inabit.compiler.parser.grammar.Symbol;
import inabit.compiler.parser.grammar.Terminal;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**Builds a predictive table automatically given the context-free grammar
 * of the language*/
/**@author Rafael Rocha*/
public class TableBuilder {
	
	private Grammar grammar;
	private HashSet<String> checkedVars;
	
	public TableBuilder(Grammar grammar) {
		this.grammar = grammar;
		checkedVars = new HashSet<String>();
	}
	
	/**Returns a predictive table, mounted based on the context-free grammar*/
	public PredictiveTable buildPreditiveTable() {
		PredictiveTable table = new PredictiveTable();
		List<Terminal> ruleTerminals = new ArrayList<Terminal>();
		
		for(Production rule : grammar.getProductionRules()) {
			checkedVars.clear();
			ruleTerminals.addAll(first(rule));
			
			if(isEmptyProduction(rule)) {
				ruleTerminals.addAll(follow(rule.getNonTerminal()));
			}
			for(Terminal terminal : ruleTerminals) {
				table.addEntry(rule, rule.getNonTerminal().getLabel(), terminal.getTokenClass());
			}
			ruleTerminals.clear();
		}
		return table;
	}
	
	/**Returns <i>true</i> if the symbol can be associated with
	 * the empty word*/
	private boolean isEmptyWord(Symbol s){
		if(s instanceof Terminal){
			return false;
		}else if(s instanceof NonTerminal) {
			return hasEmptyProduction((NonTerminal)s);
		}else {
			return true;
		}
	}
	
	/**Returns <i>true</i> if the production specified by parameter
	 * can be an empty production or <i>false</i> otherwise*/
	private boolean isEmptyProduction(Production rule) {
		for(Symbol s : rule.derive(rule.getNonTerminal())) {
			if(s instanceof Terminal) {
				return false;
			}else if(s instanceof NonTerminal) {
				if(!hasEmptyProduction((NonTerminal)s)){
					return false;
				}
			}
		}
		return true;
	}
	
	/**Returns <i>true</i> if there is at least one production on
	 * the grammar that can be an empty production*/
	private boolean hasEmptyProduction(NonTerminal nt) {
		
		for(Production rule : grammar.getProductionRules()) {
			if(rule.getNonTerminal().getLabel().equals(nt.getLabel())) {
				if(isEmptyProduction(rule)) {
					return true;
				}
			}
		}
		return false;
	}
	
	/**Return the set of firstTerminals associated with the symbol
	 * specified by parameter*/
	private Set<Terminal> first(Symbol s) {
		Set<Terminal> terminals = new HashSet<Terminal>();
		if(s instanceof Terminal) {
			terminals.add((Terminal)s);
		}else if(s instanceof NonTerminal) {
			return first((NonTerminal)s);
		}
		return terminals;
	}
	
	/**Returns the set of first terminals of the productions associated
	 * if the non terminal specified by paramater <i>nt</i>*/
	private Set<Terminal> first(NonTerminal nt) {
		Set<Terminal> firstTerminals = new HashSet<Terminal>();
		for(Production rule : grammar.getProductionRules()) {
			if(rule.getNonTerminal().getLabel().equals(nt.getLabel())) {
				firstTerminals.addAll(first(rule));
			}
		}
		return firstTerminals;
	}
	
	/**Returns the set of the first terminals of the production specified
	 * by parameter*/
	private Set<Terminal> first(Production rule) {
		Set<Terminal> firstTerminals = new HashSet<Terminal>();
		
		boolean finished = false;
		List<Symbol> symbols = rule.derive(rule.getNonTerminal());
		for(int i = 0; i < symbols.size() && !finished; i++) {
			if(symbols.get(i) instanceof Terminal) {
				finished = true;
				firstTerminals.add((Terminal)symbols.get(i));
			}else if(symbols.get(i) instanceof NonTerminal) {
				NonTerminal nt = (NonTerminal)symbols.get(i);
				firstTerminals.addAll(first(nt));
				finished = !hasEmptyProduction(nt);
			}
		}
		
		return firstTerminals;
	}
	
	/**Returns <i>true</i> if the production rule includes the non-terminal
	 * <i>nt</i> in its derivation*/
	public boolean derivesNonTerminal(Production rule, NonTerminal nt) {
		for(Symbol s : rule.derive(rule.getNonTerminal())) {
			if(s instanceof NonTerminal) {
				if(((NonTerminal)s).getLabel().equals(nt.getLabel())) {
					return true;
				}
			}
		}
		return false;
	}
	
	/**Returns the set of follow terminals of this non terminal on
	 * production rules that derives it*/
	private Set<Terminal> follow(NonTerminal nonTerminal) {
		Set<Terminal> followTerminals = new HashSet<Terminal>();
		//if this non terminal is already being checked, returns
		if(checkedVars.contains(nonTerminal.getLabel())) {
			return followTerminals;
		}
		//mark this non terminal as being checked
		checkedVars.add(nonTerminal.getLabel());
		
		//The follow of initial variable contains EOF
		if(nonTerminal.getLabel().equals(grammar.getInitialSymbol().getLabel())) {
			followTerminals.add(new Terminal(grammar.eof()));
		}
		
		//searches the rules that derive this non terminal
		for(Production rule : grammar.getProductionRules()) {
			if(derivesNonTerminal(rule, nonTerminal)) {
				List<Symbol> symbols = rule.derive(rule.getNonTerminal());
				boolean found = false;
				for(int i = 0; i < symbols.size(); i++) {
					
					//test to see if the current symbol is the non terminal
					if(symbols.get(i) instanceof NonTerminal) {
						NonTerminal nt = (NonTerminal)symbols.get(i);
						if(!found && nt.getLabel().equals(nonTerminal.getLabel())) {
							found = true;
						}
					}
					//if found the non terminal index
					if(found) {
						//if the non terminal is at the end, the follow of the production symbol
						//is contained on the follow of this non terminal
						if(i == symbols.size()-1) {
							followTerminals.addAll(follow(rule.getNonTerminal()));
						}else {//otherwise add the first terminals of the next index
							followTerminals.addAll(first(symbols.get(i+1)));
							if(!(symbols.get(i+1)instanceof SemanticAction)) {
								if(isEmptyWord(symbols.get(i+1))) {
									followTerminals.addAll(follow((NonTerminal)symbols.get(i+1)));
								}
								found = false;
							}
						}
					}
				}
			}
		}
		return followTerminals;
	}
}
